In an ATM system, the traffic from a source is transmitted in fixed-length packets called cells, containing data and header information. The cells from different sources are interleaved and transmitted along a single link. The interleaving is non-uniform, in that more cells from a particular source may be interleaved per unit time than from a second source. This allows traffic from different types of sources to use only as much bandwidth as is needed, and provides much more efficient use of the total available bandwidth. The ATM network should allocate bandwidth to the different sources of traffic according to how fast each source needs to transmit information and the desired Quality of Service (QoS). This will depend on the type of information being transmitted, and on what the user is willing to pay for.
The Connection Admission Control (CAC) mechanism of the network is responsible for determining if a connection request can be accepted. When a source attempts to make a connection to the ATM network it will specify a service category and negotiate a traffic contract with the network. The traffic contract consists of a connection traffic description, a service category, a set of QoS parameters, and a conformance definition. The connection traffic description contains two parts: a source traffic descriptor which characterizes the source traffic using a set of rate and burstness related parameters, including the Peak Cell Rate (PCR) and the Minimum Cell Rate (MCR); and the Cell Delay Variation Tolerance (CDVT) which is to be used by the network at the User-Network Interface (UNI) to account for the amount of Cell Delay Variation (CDV) when monitoring the user traffic. The negotiated QoS parameters (some parameters are not negotiated) can include the Peak-to-peak Cell Delay Variation (CDV), the Maximum Cell Transfer Delay (CTD), and the Cell Loss Ratio (CLR). The conformance definition identifies a set of predefined rules which unambiguously specify the conforming cells of the connection. If the source and the network reach agreement on the QoS for the requested traffic descriptor and service category, a connection is established.
The service category specifies broadly the manner in which the cell transmission rate is to vary, if at all. One of the possible service categories is Available Bit Rate (ABR). In ABR additional parameters are negotiated at call set-up: the Initial Cell Rate (ICR), the ADTF (described below), the RIF (described below), and the RDF (described below). In ABR the user requests a Minimum Cell Rate (MCR) and specifies a Peak Cell Rate (PCR) and an Initial Cell Rate (ICR). The CAC evaluates the capacity of the network and the current traffic on the network to determine if this minimum cell rate can be guaranteed to the user. In the meantime, network elements may directly modify the ICR to a lower value if needed, and provide delay and buffer space information which enables the source to recompute an updated ICR which should be no higher than the ICR originally requested by the source. If the MCR can be guaranteed, a connection will be established and the source can begin transmitting at the updated ICR. During transmission the available bandwidth in the network may decrease due to higher bandwidth consumption by services that enjoy a higher service priority than ABR, and the source will be instructed to lower its cell transmission rate. At other times more capacity may become available due to the dropping of other calls or the variation of cell rate of other connections. In effect, the source is always allowed to transmit cells at the MCR, but can transmit cells at a higher rate as bandwidth becomes available. ABR is not intended to support real-time applications. The QoS can remain unspecified since Cell Delay Variation and Cell Transfer Delay are unimportant, and the Cell Loss Ratio is expected to be very low as long as the source transmits within the cell rate specified at any given time by the network. The negotiation at connection set-up of an ABR call consists simply of a request by the source for a connection based on a specified MCR and PCR, and a determination by the network as to whether it can offer a very low CLR for the specified MCR. If it can, the CAC system will inform the source that it can offer a cell transmission rate at least as great as the MCR, and a very low CLR as long as the source complies with the cell transmission rate specified by the network from time to time.
During the transmission, the source must be informed of any changes in its Allowed Cell Rate (ACR), the rate at which the source is allowed to transmit cells at any given time. This is done actively by the source, which periodically polls the network to determine the ACR. The frequency with which this is done is determined by the value of Nrm, a parameter negotiated during call set-up. This is the maximum number of cells that the source can transmit for each Forward Resource Management (F-RM) cell. A F-RM cell is transmitted by the source to convey resource management information between the source, the network elements, and the destination. It carries a requested cell rate value (typically the PCR) in the cell's Explicit Rate (ER) field. When the F-RM cell reaches the destination, it is turned around and sent back to the source as a Backward Resource Management (B-RM) cell, carrying feedback information provided by the network elements and the destination. As the B-RM cell passes through each network element on its way back to the source, the network element compares the value in the ER field of the B-RM cell with the cell rate that the network element can offer. If the network element can only offer a cell rate less than the value contained in the ER field, the network element substitutes its offered cell rate for that in the B-RM cell. One type of network element, a binary switch, is not capable of providing exact ER information. Instead, a binary switch examines its buffer to derive congestion information and indicates to the source indirectly that it should perform a relative rate increase or decrease. If the binary switch detects congestion it sets the Explicit Forward Congestion Indication (EFCI) state of the data cell to "1" by altering the Payload Type Identifier field in the header of the data cell. The EFCI of each data cell is monitored by the destination. When the destination receives a new F-RM cell it checks whether the EFCI state of the immediately preceding data cell was "1". If so, the destination sets the Congestion Indication (CI) and No Increase (NI) fields of the B-RM cell to "1".
By the time the B-RM cell returns to the source it carries the value of the lowest cell rate offered by any of the network elements and carries binary flags indicating if there is congestion in any binary switches. The source computes its ACR as the minimum of the Explicit Rate (ER) offered by the network and a locally computed rate which is a function of the previous ACR, the presence of congestion in the network as indicated by the CI and NI fields in the B-RM cell, and the Rate Increase Factor (RIF) and Rate Decrease Factor (RDF) negotiated during call set-up. The computed ACR is the cell rate at which the source should then transmit, as it is the highest bandwidth that the network as a whole can guarantee for the connection.
An honest source will adapt its transmission rate to match the ACR, thereby ensuring a low CLR and usage of its fair share of the overall available bandwidth. However non-compliant sources will transmit cells at a rate higher than the ACR in hopes of obtaining a higher share of the bandwidth than that to which they are entitled. To prevent this the network must carry out a function called policing. Policing is carried out at the User Network Interface (UNI) Usage Parameter Control (UPC) which a set of traffic monitor and control functions. When a B-RM cell leaves the network through the UNI on its way to the source, the UPC takes note of the ER contained in the B-RM cell. Thereafter the UPC polices the traffic from the source and enforces the allowed rate in order to prevent the source from abusing the network. Traffic policing in general has two aspects: detecting excessive cells that do not conform to the rate limits provided by the network; and taking actions against the non-conforming cells that are detected. In ABR the only action available upon detection of non-conforming cells is the discarding of the non-conforming cells.
The source is expected to poll the network for a new ER at a minimum frequency. Otherwise the source, upon being instructed of a particularly high ACR at some point, could take advantage of this extra bandwidth indefinitely by transmitting no more F-RM cells. If no F-RM cells were transmitted then the UPC would see no new B-RM cells and would continue to police at the high cell rate even though available bandwidth may have dropped. The source would be using more than its fair share of network bandwidth indefinitely. To avoid this, the frequency at which F-RM cells are transmitted is regulated. The Nrm is a parameter specifying the maximum number of cells that a source may send for each F-RM cell. The network dynamically allocates unused bandwidth to active connections to achieve high resource utilization. A source which has a high ACR but actually transmits at a very low rate or remains idle for a long period of time will have its unused bandwidth quota allocated to others by the network. To prevent this source from suddenly transmitting at the high ACR rate and overloading the network, the ACR Decrease Time-out Factor (ADTF) is defined as the maximum time permitted between sending F-RM cells before the source is required to lower its rate to ICR, if the current ACR is greater than ICR. The Nrm and ADTF are part of the ABR set-up parameters negotiated at call set-up.
The standard algorithm used by the UPC to detect excess cell rates is called the Generic Cell Rate Algorithm (GCRA). The ATM Forum Technical Committee has proposed two equivalent versions of the GCRA for detecting cells that exceed a policed rate. These algorithms are provided in section 4.4.2 of the ATM Forum Traffic Management Specification, Version 4.0 (the "ATM Forum"). If the rate to be policed varies with time, as is the case with ABR traffic, then the GCRA must be dynamic. Two Dynamic GCRAs (DGCRAs) are proposed for ABR policing in Informative Appendix III of the ATM Forum, and are discussed in more detail below.
If the UPC could enforce a new ER immediately upon being informed of the new ER (by reading the B-RM cell) then the algorithm for enforcing the ER would be relatively straightforward. The UPC would simply vary the parameters of the DGCRA immediately upon learning of a new ER to be enforced. However the UPC must delay enforcement of a new ER because time must elapse between the time of detection of the new ER by the UPC and the time that the effects of the new ER appear at the UPC on the forward link from the source. This response delay must account for the time necessary for the B-RM cell containing the new ER to propagate along the transmission medium from the UNI to the source, the time necessary for the source to adapt its transmission rate after processing the new ER information and calculating its ACR, and the time necessary for the first cells transmitted at the new computed ACR to propagate along the transmission medium from the source to the UNI. Only then should the UPC begin enforcing the new ER. The delay time is calculated by the UPC based on the network configuration, and is bounded by an upper limit .tau..sub.2 and a lower limit .tau..sub.3. These two limits could be obtained through measurement statistics. Any doubt as to when to begin enforcement of the new ER is resolved in favour of the user. If the ER is decreasing from its previous value then the UPC will delay enforcement of the new ER by the upper delay limit in order to ensure that cells transmitted by an honest source are not rejected before the source has had a chance to put the new ER into effect. If the ER is increasing from its previous value then the UPC will delay enforcement of the new ER by the lower delay limit, in case the honest source puts the new ER into effect in the shortest time possible.
As described above, a new ER typically becomes available every Nrm-1 data cells, where according to the ATM Forum the default value of Nrm is 32. With high speed transmission and typical delay times, it is almost inevitable that a second new ER will become available before enforcement of an earlier new ER has begun. For example, consider a UPC enforcing a current Policing Rate (PR). At some time t.sub.b (i) a B-RM cell reaches the UPC indicating that a new ER (ER(i)) is available. The UPC determines that this is a decrease in ER (for example) and schedules an enforcement time of t(i)=t.sub.b (i)+.tau..sub.2, where .tau..sub.2 is the upper limit of the response delay. At some later time t.sub.b (i+1) a second B-RM cell reaches the UPC indicating that a second new ER (ER(i+1)) is available. This is an increase in ER (for example) from the value of ER(i), so the UPC schedules an enforcement time of t(i+1)=t.sub.b (i+1)+.tau..sub.3, where .tau..sub.3 is the lower limit of the response delay. If t.sub.b (i+1)&lt;t(i) then enforcement of ER(i) has not yet begun. The UPC could simply discard the value of ER(i) and t(i) and replace them with ER(i+1) and t(i+1). The preferable solution is to store the values of both sets of pending enforcements. It should be noted that a time sequence anomaly can arise because of the response delays, if .tau..sub.2 and .tau..sub.3 are sufficiently far apart and consecutive B-RM cells arrive sufficiently close together. If a rate decrease is followed closely by a rate increase, such that t.sub.b (i+1)+.tau..sub.3 &lt;t.sub.b (i)+.tau..sub.2, then t(i+1)&lt;t(i) and enforcement of ER(i+1)would be scheduled to begin before enforcement of ER(i). This is not necessarily a problem, but the UPC must monitor for this anomaly.
In an ideal system the UPC would store the values of all the pending ERs and their enforcement times, and enforce each one as required. This is in fact what is proposed by the ATM Forum as Algorithm A. Depending on the response delay and link speed, the number of pending ERs and corresponding enforcement times could range from on the order of 10 to on the order of 1000. The storage of this many ERs and their enforcement times is impractical.
The ATM Forum has proposed a second DGCRA called Algorithm B, in which only two pending ERs and their enforcement times are stored. This is a compromise because as less ER information is stored, the more approximations must be made in determining the ER to enforce at any given time and the larger the potential margin between the actual ER offered by the network and the rate at which the UPC is policing. Industry has accepted this compromise of storing two pending ERs. Algorithm B must necessarily be over generous at times when making its approximations. For honest sources this is not a concern, as they will transmit only at the ER at which they have been instructed to transmit. But non-conforming sources will be able to transmit cells at a higher ER than at which they have been instructed to transmit without being detected. This is termed "cheating", and the amount of excess traffic that can be transmitted (between the ER and the over generous policed rate) is termed the "cheating room".
It is desirable to limit the cheating room as much as possible. J. Adams has proposed an improvement over Algorithm B, called Improved Algorithm B (J. Adams, "Improved Algorithm B for ABR Conformance", ATM Forum contribution 96-616R2, BT, April 1996). This somewhat reduces the amount of cheating room, although there is still room for improvement. And Improved Algorithm B in fact over-polices in some situations. Cells from honest sources can be discarded unnecessarily, as illustrated in more detail below.
Source behaviour #8 specified in the ATM Forum requires that ABR sources account for binary-oriented relative rate changes. Binary switches react to bandwidth changes in the network considerably slower than non-binary (ER) switches. As a result, the rate change required by binary switches and that by ER switches can be different. If the rate offered by ER switches is higher than the rate computed according to binary feedback information in the CI and NI fields, and if UPC only enforces ER, an abusive user can take advantage of the difference and sends traffic at ER without being detected. The excessive traffic sent by the abusive user gives the user an unfair bandwidth advantage over conforming users and can result in congestion. Abusive users can take advantage of the rate difference if there is only policing of the rate indicated by the ER switches. Neither Algorithm B nor Improved Algorithm B makes use of rate changes required by binary switches when setting the policed cell rates, and both allow the source to transmit at the ER offered by non-binary switches without considering the rate change requested by binary switches. There is therefore room for further reduction of the cheating room in paths containing binary switches.